package com.demo.java.OD401_450.OD449;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【亲子游戏(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146331885
 */
public class OdMain {
    // 定义四个方向，分别是右、下、上、左
    static int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取棋盘大小 N
        int[][] grid = new int[n][n];  // 创建 N x N 的棋盘

        int sx = 0, sy = 0, tx = 0, ty = 0;

        // 读取棋盘数据并找出起点 (sx, sy) 和终点 (tx, ty)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = scanner.nextInt();
                if (grid[i][j] == -3) {
                    sx = i;
                    sy = j;
                }
                if (grid[i][j] == -2) {
                    tx = i;
                    ty = j;
                }
            }
        }

        int level = 0;
        boolean isFind = false;
        int[][] checkList = new int[n][n];  // 记录是否已经访问
        checkList[sx][sy] = 1;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{sx, sy});

        // 使用 BFS 搜索最短路径
        while (!queue.isEmpty()) {
            int qSize = queue.size();
            for (int i = 0; i < qSize; i++) {
                int[] current = queue.poll();
                int x = current[0];
                int y = current[1];
                if (grid[x][y] == -2) {  // 如果到达终点，标记为找到路径
                    isFind = true;
                    break;
                }
                for (int[] dir : DIRECTIONS) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n && checkList[nx][ny] == 0 && grid[nx][ny] != -1) {
                        checkList[nx][ny] = 1;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
            if (isFind) {
                break;
            }
            level++;
        }

        if (!isFind) {  // 如果无法到达终点
            System.out.println(-1);
        } else {
            int[][] dp = new int[n][n];  // dp 数组记录每个位置能收集的最大糖果数量
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j] = -1;  // 初始化为 -1，表示无法到达
                }
            }
            dp[sx][sy] = 0;  // 起点糖果为 0
            queue.clear();
            queue.offer(new int[]{sx, sy});

            // 进行 BFS，计算每个位置收集的最大糖果数量
            while (level >= 0) {
                int qSize = queue.size();
                for (int i = 0; i < qSize; i++) {
                    int[] current = queue.poll();
                    int x = current[0];
                    int y = current[1];
                    for (int[] dir : DIRECTIONS) {
                        int nx = x + dir[0];
                        int ny = y + dir[1];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] != -1) {
                            if (dp[nx][ny] == -1) {
                                queue.offer(new int[]{nx, ny});
                            }
                            if (grid[nx][ny] != -2) {
                                dp[nx][ny] = Math.max(dp[nx][ny], dp[x][y] + grid[nx][ny]);  // 更新糖果数量
                            } else {
                                dp[nx][ny] = Math.max(dp[nx][ny], dp[x][y]);  // 终点不收集糖果
                            }
                        }
                    }
                }
                level--;
            }

            System.out.println(dp[tx][ty]);  // 输出终点的最大糖果数量
        }
    }
}
